# -*- coding: utf8 -*-
#!/usr/bin/env sage -python 
'''
Created on 29 janv. 2012

@author: elix

Implement with "Introduction to Automata Theory, Languages and Computation" written by 
John E. Hopcroft, Rejeev Motwani and Jeffrey D.Ullman.
'''
from sage.misc.abstract_method import abstract_method

class Automata(object):
    def __init__(self, A, Q, i, F, delta):
        self.__alphabet = set(A)
        self.__states = set(Q)
        self.__initial = i
        self.__accepting_states = set(F)
        for q in F :
            assert q in self.__states
        self.__delta = delta
       
    @abstract_method
    def __delta_parse(self, delta):
        r''' '''
    
    @abstract_method
    def delta_function(self):
        r''' It's a distinct function between DFA and NFA
        '''
    def get_alphabet(self):
        return self.__alphabet
    
    def get_states(self):
        return self.__states
    
    def get_initial(self):
        return self.__initial
    
    def get_accepting_states(self):
        return self.__accepting_states
    
    @abstract_method
    def recognizes(self, w):
        r''' Compute if w is recognized by the automata
        '''
    @abstract_method
    def __add__(self, automata):
        r''' Overload +
        Make a language union of self and automata
        '''
        
    @abstract_method
    def __mul__(self, automata):
        r''' Overload *
        Make a language concatenation of self then automata 
        '''
        
class DFA(Automata):
    r''' A deterministic finite automaton consists of :
     - A finite set of input symbols : A (@param A: An iterable containing the symbols in the DFA's alphabet)
     - A finite set of states : Q (@param Q: An iterable containing the states of the DFA)
     - An initial state : i (@param i : in Q)
     - A set of accepting states : F (@param F: a subset of Q)
     - A transition function : delta_function (@param delta_function: must be a function which take a state and a symbol 
     from Q and A to Q)
    EXAMPLES::
        sage: trans = {0 : {0 : 1}, 1 : {0 : 0}}
        sage: delta = lambda x,y : trans[x][y]
        sage: M = DFA(range(2), range(3), 0, [0], delta)
    '''
    
    def __init__(self, A, Q, i, F, delta):
        r'''
        '''
        Automata.__init__(self, A, Q, i, F, delta)
        self.__delta = {}
        self.__delta_parse(delta)
        
    def __delta_parse(self, delta):
        r''' @attention: can return KeyError
        '''
        for q in Automata.get_states(self) : 
            for a in Automata.get_alphabet(self) :
                try : self.__delta[q]
                except :
                    self.__delta[q] = {}
                try :
                    self.__delta[q][a] = delta[q][a]
                except :
                    # modify if you want complete automata
                    pass
    
    def delta_function(self, p, a):
        r'''
        @todo: retourner une erreur ou non??? si oui quelle erreur?
        '''
        try :
            return self.__delta[p][a]
        except KeyError :
            return None
    
    def recognizes(self, w):
        r''' 
        Compute if it exists a sequence of transition from the initial state to an accepting state
        @param w: an iterable containing symbol in A 
        @return: true if and only if w is recognized
        '''
        p = Automata.get_initial(self)
        for a in w :
            p = self.delta_function(p, a)
            if p is None : return False
        return True if p in Automata.get_accepting_states(self) else False
    
# An automata which recognize multiple of 3 in binary.    
M = DFA(range(2), range(3), 0, [0], 
        {0 : [0, 1], 
         1 : [2, 0],
         2 : [1, 2]})
print M.recognizes([1,0,0,1]) #9 = 3 x 3 -> True
print M.recognizes([1,1,0,0,1,1,0]) # 51 = 3 x 17 -> True
print M.recognizes([0,1,0,0,1,1,0]) # 50 -> False

class NFA(Automata):
    r''' A nondeterministic finite automata consist of :
     - A finite set of input symbols : A (@param A: An iterable containing the symbols in the DFA's alphabet)
     - A finite set of states : Q (@param Q: An iterable containing the states of the DFA)
     - An initial state : i (@param i : in Q)
     - A set of accepting states : F (@param F: a subset of Q)
     - A transition function : delta_function (@param delta_function: must be a function which take a state and a symbol 
     from Q and A to a subset of Q)
     EXAMPLES::
        sage: trans = {0 : {0 : [2,1]}, 1 : {0 : [0,1]}}
        sage: delta = lambda x,y : trans[x][y]
        sage: M = NFA(range(2), range(3), 0, [0], delta)
    '''
    
    def __init__(self, A, Q, i, F, delta):
        r'''
        '''
        Automata.__init__(self, A, Q, i, F, delta)
        self.__delta_parse(delta)
        
    def __delta_parse(self, delta):
        r''' @attention: can return KeyError
        '''
        self.__delta = {}
        for q in Automata.get_states(self) :
            for a in  Automata.get_alphabet(self) :
                try : self.__delta[q]
                except KeyError :
                    self.__delta[q] = {}
                self.__delta[q][a] = set()
                try :
                    st = delta[q][a]
                    for p in st : 
                        self.__delta[q][a].add(p)
                except KeyError :
                    # modify if you want complete automata
                    pass
   
    def delta_function(self, p, a):
        try :
            return self.__delta[p][a]
        except KeyError :
            return set()
        
    def recognizes(self, w):
        r''' 
        Compute if it exists a sequence of transition from the initial state to an accepting state
        @param w: an iterable containing symbol in A 
        @return: true if and only if w is recognized
        '''
        tp = [Automata.get_initial(self)]
        tq = None
        for a in w :
            temp = set()
            for p in tp :
                try :
                    tq = self.delta_function(p, a)
                    temp = temp.union(tq)
                except KeyError :
                    pass
            tp = temp
        if len(tp.intersection(self.get_accepting_states())) == 0 :
            return False 
        return True

# The Glushkov automata of E = (a+b)*a    
M = NFA(['a','b'], range(4), 0, [3], 
        {0 : {'a' : [1,3], 'b' : [2]}, 
         1 : {'a' : [1,3], 'b' : [2]},
         2 : {'a' : [1,3], 'b' : [2]}})
print M.recognizes("abbba") # True
print M.recognizes("aaabbbbbbab") # False

    
def determinizes(nfa):
    r''' Compute a DFA with a NFA.
    TODO trouver un algorithme efficace
    '''
    # A DFA which recognizes emptyset
    det = DFA(nfa.get_alphabet(), [0], 0, [], [])
    # mapping...
    
determinizes(M)

def minimized(dfa):
    r''' Compute the minimal DFA of dfa
    TODO implanter Hopcroft?
    '''
    
''' TODO
    Ajouter quoi d'autres??? 
    Mettre en place ER -> Automate : quel algo?
    Mettre en place Automate -> Semi-groupe syntaxique : ya des algo pas trop bourrin?
    ...
'''